package LeetCode.t20;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author: Laity
 * @Project: JavaLaity
 * @Package: LeetCode.t20.IsValid
 * @Date: 2022年11月12日 19:35
 * @Description: LeetCode第20题：有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 */
public class IsValid {

    public static boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                //获取但不删除栈顶元素 ：stack.getFirst() - c 根据ASCII码表
                if (stack.size() != 0 && Math.abs(stack.getFirst() - c) <= 2) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static boolean isValid1(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        Map<String, String> map = new HashMap<>();
        map.put("(", ")");
        map.put("{", "}");
        map.put("[", "]");
//        Map<String, String> map1 = new HashMap<>();
//        map1.put(")", "(");
//        map1.put("]", "[");
//        map1.put("}", "{");


        // 两种情况
        String s1 = map.get(s.charAt(0) + "");
        String s2 = s.charAt(s.length() - 1) + "";
        if (s1 == null) {
            return false;
        }
        // "(}{)"
        boolean equals = s1.equals(s2);
        if (equals) {
            int len = s.length() / 2;
            for (int i = 1; i < len; i++) {
                String s3 = map.get(s.charAt(i) + "");
                if (!s3.equals(s.charAt(s.length() - (i + 1)) + "")) {
                    return false;
                }
            }
        } else {
            // "(){}}{"
            for (int i = 0; i < s.length(); i += 2) {
                String val = map.get(s.charAt(i) + "");
                // String end = map.get(s.charAt(i + 1) + "");
                String end = s.charAt(i + 1) + "";
                if (val == null || !val.equals(end)) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "[[[[]]]]";
        System.out.println(isValid(s));
    }
}
